//归并排序
void recursion(int left, int right, int* arr, int* new_arr)
{
	if (left >= right) {
		return;
	}
	int mid = left + (right - left) / 2;
	recursion(left, mid, arr, new_arr); //递归式传参要注意避免栈溢出，[left,mid]和[mid+1,right]
	recursion(mid+1, right, arr, new_arr);
	int begin1 = left, begin2 = mid+1;
	int end1 = mid, end2 = right;
	int cur1 = begin1, cur2 = begin2;
	int cur = left;
	while (cur1 <= end1 || cur2 <= end2) {
		if (cur1 <= end1 && cur2 <= end2) {
			if (arr[cur1] > arr[cur2]) {
				new_arr[cur++] = arr[cur2++];
			}
			else
			{
				new_arr[cur++] = arr[cur1++];
			}
		}
		else if (cur1 <= end1) {
			new_arr[cur++] = arr[cur1++];
		}
		else {
			new_arr[cur++] = arr[cur2++];
		}
	}
	//然后将new_arr数组中的数据拷贝到arr中
	int size = right - left + 1;
	memcpy(arr+left, new_arr+left, size * sizeof(int)); //这里需要注意：拷贝数据的起始位置必须正确
}
void mergeSort(int arr[], int size)
{
	int* new_arr = new int[size] {0};
	recursion(0, size - 1,arr, new_arr);
	delete[] new_arr;
	return;
}